Parallel computing systems consist of a plurality of processors that communicate via an interconnection network. One popular network for providing the interconnection for a plurality of processors is the circuit-switched network comprised of multiple circuit switches. The state-of-the-art unbuffered circuit switch is the ALLNODE Switch (Asynchronous, Low Latency, inter-NODE switch), which is disclosed in U.S. Ser. No. 07/677,543. The Allnode switch as disclosed in U.S. Ser. No. 07/677,543 provides excellent low latency characteristics because it implements a minimum amount of circuitry at each switch stage of a multi-stage interconnection network. The latency across the switch is extremely fast because the equivalent of a straight wire connection is provided across each switch stage without involving any relatching at each switch stage. No relatching of data is required since the Allnode Switch supports a totally asynchronous transmission that does not require relatching or buffering at the individual switch elements. Therefore, the Allnode Switch delivers data messages being transmitted through the switch as quickly as possible avoiding the delays of any buffering.
The problem with the unbuffered, asynchronous method is that the data transmission pulses passing through each switch stage are not reshaped or realigned by a relatching process. As the signals pass through multiple switch stages, the original pulse shape can get distorted. Also, data that is transferred in parallel (such as byte wide transfers) can experience skew amongst the parallel data bits, because the parallel lines are not realigned at every stage of the network. These two problems of pulse distortion and skewing limit the frequency of the transmission and the number of stages of network that can be traversed before the pulses become too distorted or skewed to be reliable.
The solving of distortion and skewing problems can create other problems if not handled correctly, such as introducing too much latency or too much unreliability into the solution to make it viable. An important feature of the ALLNODE switch is that it is very reliable and there are no common signals or components in the switch that can fail the whole switch chip. Introducing a common clock used by every port of the switch is not an acceptable solution, because a failure of that clock would fail the entire switch chip. Also, since the ALLNODE switch is an asynchronous design, care must be taken not to use a solution that would increase the chances of encountering a metastability condition because of new metastability opportunities that could be created while attempting to solve the distortion and skew problem. The present invention discloses a method and apparatus for circumventing these problems, while solving the distortion and skewing problems.
The present invention is a modification and adaption of the ALLNODE switch, as disclosed the parent application, U.S. Ser. No. 07/677,543. We will further describe in the detailed description the relationship between the present invention and the parent application.